-
41 дерево (в теории графов)
дерево (в теории графов)
В теории графов ? связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n — 1 ребро, не имеет циклов; если добавить ребро, соединяющее две несмежные вершины, то образуется один цикл; при удалении любого ребра граф становится несвязным; каждая пара вершин соединяется одной и только одной цепью. Исходная вершина называется корнем, пути от нее к крайним вершинам — ветвями. Примеры см. в статьях: Дерево игры, Дерево решений, Дерево целей.
[ http://slovar-lopatnikov.ru/]Тематики
EN
Русско-английский словарь нормативно-технической терминологии > дерево (в теории графов)
-
42 cutset
разрез (для вершин v и w неориентированного графа - подмножество рёбер графа такое, что любой путь из v в w содержит элемент этого подмножества)Англо-русский словарь промышленной и научной лексики > cutset
-
43 букет
( совокупность вершин отдельного связного компонента графа) blossom т.граф.Русско-английский словарь по вычислительной технике и программированию > букет
-
44 depth-first search
поиск типа «сначала - вглубь»Англо-русский словарь промышленной и научной лексики > depth-first search
-
45 цепь
цепь
Гибкое изделие, состоящее из отдельных последовательно соединённых жёстких звеньев. Схема последовательности элементов.
[ http://sl3d.ru/o-slovare.html]
цепь
Термин теории графов, последовательность ребер графа — такая, что для каждого ребра, кроме первого и последнего, одна из его вершин является общей с предыдущим ребром, а вторая — с последующим. Ц. называется простой, если каждое ребро встречается не более одного раза, в противном случае — сложной. Число ребер — n называется длиной цепи.
[ http://slovar-lopatnikov.ru/]Тематики
EN
Русско-английский словарь нормативно-технической терминологии > цепь
-
46 цикломатическое число
цикломатическое число
Термин теории графов, одна из возможных числовых характеристик несвязного графа. Если граф X имеет n вершин, m ребер, а p — количество его связных частей — компонент (см. Граф), то Ц.ч. определяется равенством v(X) = m — n + p. При Ц.ч., равном нулю, граф не содержит циклов, если же оно равно единице, то граф имеет только один цикл.
[ http://slovar-lopatnikov.ru/]Тематики
EN
Русско-английский словарь нормативно-технической терминологии > цикломатическое число
См. также в других словарях:
ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… … Математическая энциклопедия
ГРАФА РАСКРАСКА — приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска это раскраска вершин (ребер) графа, при к рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную… … Математическая энциклопедия
ГРАФА УКЛАДКА — графа вложение, отображение вершин и ребер графа соответственно в точки и непрерывные кривые нек рого пространства такое, что вершины, инцидентные ребру, отображаются в концы кривой, соответствующей этому ребру. Правильной укладкой наз. укладка,… … Математическая энциклопедия
ГРАФА ОБХОД — маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами. Наиболее известными Г. о. являются эйлеровы и гамильтоновы цепи и циклы. Маршрут (замкнутый маршрут) наз. эйлеровой … Математическая энциклопедия
ГРАФА АВТОМОРФИЗМ — изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой… … Математическая энциклопедия
Медиана графа — Связать? Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная. Пусть необходимо выбрать место для размещения телефонного коммутатора, электроподстанции, баз снабжения в сети дорог или… … Википедия
Разбиение графа — Пример разбиения параллельной граф схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется… … Википедия
Раскраска графа — 3 раскраска графа Петерсена Хроматическое число графа G минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G). Содержание 1 Определение … Википедия
Максимальное независимое множество вершин в дереве — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… … Википедия
Разрез графа — в задачах о потоке такая пара множеств вершин (S,T), что , где множество вершин графа , где исток, сток. Величиной разреза называется сумма пропускных способностей таких рёбер … Википедия
Компонента связности графа — Несвязный граф с тремя компонентами связности Компонента связности графа некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества … Википедия